class Solution:
    def maxNumber(self, nums1, nums2, k: int):
        def pickMax(nums, x):
            if len(nums) == x:
                return nums
            elif len(nums)<x:
                return []
            if x == 0:
                return []
            stack = []
            i = 0
            while i < len(nums):
                if len(stack) == 0:
                    stack.append(nums[i])
                else:
                    if stack[-1] < nums[i] and len(stack) + len(nums) - 1 - i>=x:
                        stack.pop(-1)
                        continue
                    if len(stack) < x:
                        stack.append(nums[i])
                i += 1
            return stack

        def merge(a,b):
            a1 = 0
            b1 = 0
            r = []
            while a1<len(a) or b1<len(b):

                if a[a1:] >= b[b1:]:
                    r.append(a[a1])
                    a1+=1
                else:
                    r.append(b[b1])
                    b1+=1

            return r
        maxNum = []
        for i in range(min(len(nums1),k)+1):
            n1 = pickMax(nums1, i)
            i2 = k-i
            if i2>len(nums2):
                continue
            n2 = pickMax(nums2,i2)
            n3 = merge(n1,n2)
            maxNum = max(maxNum,n3)
        return maxNum





if __name__ == '__main__':
    so = Solution()
    nums1 = [2,5,6,4,4,0]
    nums2 = [7,3,8,0,6,5,7,6,2]
    k = 15
    r = so.maxNumber(nums1, nums2, k)
    print(r)
